/* 1007:DNA排序 */
/*
描述
现在有一些长度相等的DNA串（只由ACGT四个字母组成），请将它们按照逆序对的数量多少排序。
逆序对指的是字符串A中的两个字符A[i]、A[j]，具有i < j 且 A[i] > A[j] 的性质。如字符串”ATCG“中，T和C是一个逆序对，T和G是另一个逆序对，这个字符串的逆序对数为2。

输入
第1行：两个整数n和m，n(0<n<=50)表示字符串长度，m(0<m<=100)表示字符串数量

第2至m+1行：每行是一个长度为n的字符串
输出
按逆序对数从少到多输出字符串，逆序对数一样多的字符串按照输入的顺序输出。
*/

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

typedef struct{
    char a[55];
    int adj;
    int num;
}node;
node p[110];
int ant;
bool comp(node a, node b){
    if(a.num == b.num)
        return a.adj < b.adj;
    return a.num < b.num;
}
void merge_sort(int *A, int x, int y, int *T){
    if(y - x > 1)
    {
        int m = x + (y - x) / 2;
        int p = x, q = m, i = x;
        merge_sort(A, x, m, T);
        merge_sort(A, m, y, T);
        while(p < m || q < y)
        {
            if(q >= y || (p < m && A[p] <= A[q]))
                T[i++] = A[p++];
            else
            {
                T[i++] = A[q++];
                ant += m - p;
            }
        }
        for(i = x; i < y; ++i)
        {
            A[i] = T[i];
        }
    }
}
int main(void){
    int n, m;
    int A[55];
    int T[55];
    scanf("%d %d", &n, &m);
    getchar();
    for(int i = 0; i < m; ++i)
    {
        scanf("%s", p[i].a);
        for(int j = 0; j < n; ++j)
        {
            A[j] = p[i].a[j] - 'A';
        }
        ant = 0;
        merge_sort(A, 0, n, T);
        p[i].num = ant;
        p[i].adj = i;
    }
    sort(p, p + m, comp);
    for(int i = 0; i < m; ++i)
    {
        printf("%s\n", p[i].a);
    }
}

// Accepted
